//
// Created by X1770 on 2022/7/27.
//
//
// Created by X1770 on 2022/7/21.
//

typedef int STDateType;
typedef struct Stack
{
    STDateType* a;
    int top;
    int capacity;
}ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDateType x);
void StackPop(ST* ps);
STDateType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSzie(ST* ps);


void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}
void StackDestory(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDateType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * newCapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }

        ps->a = tmp;
        ps->capacity = newCapacity;
    }

    ps->a[ps->top] = x;
    ps->top++;
}

void StackPop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}
STDateType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));

    return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
    assert(ps);

    return ps->top == 0;
}
int StackSzie(ST* ps)
{
    assert(ps);

    return ps->top;
}




int callCount = 0;

void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void AdjustDown(int* a, int size, int parent)
{
    int child = parent * 2 + 1;
    while(child < size)
    {
        //if( (child+1)< size && a[child+1] < a[child])//小堆
        if( (child+1)< size && a[child+1] > a[child])//大堆
        {
            ++child;
        }
        //if(a[child] < a[parent])//小堆
        if(a[child] > a[parent])//大堆
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

// 升序，建大堆， 降序，建小堆
void HeapSort(int* a, int n)
{
    //建堆方式1：O（N*logN）
//    for(int i = 1; i < n; ++i)
//    {
//        AdjustUp(a, i);
//    }
    //建堆方式2：O（N）
    for(int i = (n - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDown(a, n, i);
    }

    //O（N*logN）
    int end = n - 1;
    while(end)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        --end;
    }
}

void PrintfArray(int* a, int n)
{
    for(int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void InsertSort(int* a, int n)
{
    for(int i = 0; i < n - 1; ++i) {
        //[0,end]有序,把end+1位置的数据插入，依然保持有效
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0) {
            if (tmp < a[end]) {
                a[end + 1] = a[end];
                --end;
            } else {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

void ShellSort(int* a, int n)
{
    int gap = n;
    while(gap > 1)
    {
        gap = gap / 3 + 1;
        for(int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end+gap];
            while(end >= 0)
            {
                if(tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

//void BubbleSort(int* a, int n) {
//    for (int i = 0; i < n; i++) { //确定排序趟数
//        for (int j = i + 1; j < n; j++) { //确定比较次数
//            if (a[i] > a[j]) { //交换
//                Swap(&a[i], &a[j]);
////                int temp = a[i];
////                a[i] = a[j];
////                a[j] = temp;
//            }
//        }
//    }
//}

void BubbleSort(int* a, int n)
{
    for(int j = 0; j < n - 1; ++j)
    {
        int exchange = 0;
        for (int i = 1; i < n - j; ++i)
        {
            if (a[i] < a[i - 1])
            {
                Swap(&a[i], &a[i - 1]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }

}


void SelectSort(int*a, int n)
{
    assert(a);
    int begin = 0, end = n - 1;
    while(begin < end) {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; ++i)
        {
            if (a[i] < a[mini])
                mini = i;
            if (a[i] > a[maxi])
                maxi = i;
        }

        Swap(&a[mini], &a[begin]);
        if (maxi == begin)//如果最大值和begin重合,更新maxi的位置
            maxi = mini;
        Swap(&a[maxi], &a[end]);
        --end;
        ++begin;
    }
}


//快速排序优化：三数取中
int GetMidIndex(int*a ,int begin, int end)
{
    int mid = (end - begin) / 2 + begin;
    if(a[mid] < a[begin])
    {
        if(a[mid] > a[end])
            return mid;
        else if(a[begin] < a[end])
            return begin;
        else
            return end;
    }
    else// a[mid] >= a[begin]
    {
        if(a[mid] < a[end])
            return mid;
        else if(a[begin] > a[end])
            return begin;
        else
            return end;
    }
}

//hoare
int PartSort1(int* a, int left, int right)
{
    int keyi = left;
    //基准值在三数取中
    int midi = GetMidIndex(a, left, right);
    Swap(&a[keyi], &a[midi]);
    while(left < right)
    {
        //右边先走,找到比a[keyi]小的停下来
        while(left < right && a[right] >= a[keyi])
        {
            --right;
        }
        //左边再走,找到比a[keyi]大的停下来
        while(left < right && a[left] <= a[keyi])
        {
            ++left;
        }
        Swap(&a[left], &a[right]);
    }
    Swap(&a[left], &a[keyi]);
    keyi = left;

    return keyi;
}

//挖坑法
int PartSort2(int*a, int left, int right)
{
    int midi = GetMidIndex(a, left, right);
    Swap(&a[left], &a[midi]);

    int key = a[left];
    int piti = left;
    while(left < right)
    {
        while(left < right && a[right] >= key)//右边先走，找小
        {
            --right;
        }
        a[piti] = a[right];
        piti = right;
        while(left < right && a[left] <= key)//左边再走，找大
        {
            ++left;
        }
        a[piti] = a[left];
        piti = left;
    }

    a[piti] = key;
    return piti;
}

//前后指针
int PartSort3(int* a, int left, int right)
{

    /*将基准值定在left
    int keyi = left;*/

    int prev = left;
    int cur = left + 1;
    int keyi = left;

    //基准值在三数取中
    int midi = GetMidIndex(a, left, right);
    Swap(&a[keyi], &a[midi]);

    while(cur <= right)
    {
        if(a[cur] < a[keyi] && ++prev != cur)
            Swap(&a[prev], &a[cur]);
        ++cur;
    }
    Swap(&a[prev], &a[keyi]);
    keyi = prev;

    return keyi;
}

void QuickSort(int* a, int begin, int end)
{
    //callCount++;
    if(begin >= end)
        return;

    if(end - begin > 10)//快排优化：小区间优化，减少递归
    {
        int keyi = PartSort2(a, begin, end);
        //[begin, keyi-1] keyi [keyi+1, end]
        QuickSort(a, begin, keyi - 1);
        QuickSort(a, keyi + 1, end);
    }
    else
    {
        InsertSort(a+begin, end - begin + 1);
    }
}

//快排非递归版本
//用栈模拟递归过程
void QuickSortNonR(int* a, int begin, int end)
{
    ST st;
    StackInit(&st);

    //先将最初的end,begin入栈 end先入栈,begin后入栈, 出栈顺序:begin -> end
    StackPush(&st, end);
    StackPush(&st, begin);
    int keyi,left,right;
    while(!StackEmpty(&st))
    {
        left = StackTop(&st);
        StackPop(&st);
        right = StackTop(&st);
        StackPop(&st);
        if(right -left < 10)
        {
            //callCount++;
            InsertSort(a+left, right - left + 1);
//            printf("left=%d right=%d:", left, right);
//            printf("InsertSort(a+left, right - left + 1)\n");
        }
        else
        {
            //callCount++;
//            printf("left=%d right=%d:", left, right);
//            printf("Stack\n");
            keyi = PartSort1(a, left, right);
            //[left, keyi-1] keyi [keyi+1, right]
            if(keyi + 1 < right)
            {
                StackPush(&st, right);
                StackPush(&st, keyi + 1);
            }
            if(left < keyi - 1)
            {
                StackPush(&st, keyi - 1);
                StackPush(&st, left);
            }
        }
    }
    StackDestory(&st);
}

//归并排序
void _MergeSort(int* a, int left, int right, int* tmp)
{
    if(left >= right)
        return;

    int mid = (right - left) /2 + left;
    //[left,mid] [mid,right]分治,分成两个小区间
    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid+1, right, tmp);
    //       i
    //归并    1 3 5 7 | 2 4 6 8
    int left1 = left, right1 = mid;
    int left2 = mid+1, right2 = right;
    int i = left1;
    while(left1 <= right1 && left2 <= right2)
    {
        if(a[left1] < a[left2])
        {
            tmp[i++] = a[left1++];
        }
        else
        {
            tmp[i++] = a[left2++];
        }
    }
    // 处理剩下的数据 例如: [1,3,5,7][2,4,6]
    while(left1 <= right1)
    {
        tmp[i++] = a[left1++];
    }
    while(left2 <= right2)
    {
        tmp[i++] = a[left2++];
    }

    //把归并好的数据,copy回原数组
    memcpy(a+left, tmp+left, (right-left+1)*sizeof(int));
}

void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if(tmp == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }

    _MergeSort(a, 0, n-1, tmp);

    free(tmp);
}

//归并改非递归

/**
 * gap = 1
 * i = 0
 * [0,0] [1,1]
 * [i,i+gap-1] [i+gap,i+2*gap-1]
 * i+2
 * i = 2
 * [i,i+gap-1] [i+gap,i+2*gap-1]
 * [2,2][3,3]
 *
 * gap = 2
 * i = 0
 * [0,1] [2,3]
 * [i,i+gap-1] [i+gap,i+2*gap-1]
 * [4,5] [5,6]
 * i = i + gap*2
 *
 */

void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if(tmp == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }

    int gap = 1;
    while(gap < n)
    {
        //printf("gap = %d--->", gap);
        for (int i = 0; i < n; i += gap * 2)
        {
            //[i,i+gap-1] [i+gap,i+2*gap-1]
            int left1 = i, right1 = i + gap - 1;
            int left2 = i + gap, right2 = i + 2 * gap - 1;
            int j = left1;

            //处理越界情况
            if(right1 >= n)
            {
                right1 = n - 1;
                left2 = n;
                right2 = n - 1;//[n, n-1]给不存在的区间
            }
            else if(left2 >= n)
            {
                left2 = n;
                right2 = n - 1; //[n, n-1]给不存在的区间
            }
            else if(right2 >= n)
            {
                right2 = n - 1;
            }
            //printf("[%d, %d] [%d, %d]---",left1,right1,left2,right2);
            while (left1 <= right1 && left2 <= right2)
            {
                if (a[left1] < a[left2])
                    tmp[j++] = a[left1++];
                else
                    tmp[j++] = a[left2++];

            }
            while (left1 <= right1)
                tmp[j++] = a[left1++];

            while (left2 <= right2)
                tmp[j++] = a[left2++];
        }
        memcpy(a, tmp, sizeof(int)*n);
//        printf("\n");
//        for(int i = 0; i <= end; ++i)
//        {
//            printf("%d ",tmp[i]);
//        }
//        printf("\n");
        gap*=2;
    }

    free(tmp);
}



void PrintfArray(int* a, int n);
//void InsertSort(int* a, int n);
//void ShellSort(int* a, int n);
//void HeapSort(int* a, int n);
//void BubbleSort(int* a, int n);
//void SelectSort(int*a, int n);
//void QuickSort(int* a, int begin, int end);
//void QuickSortNonR(int* a, int begin, int end);
//void MergeSort(int* a, int n);
//void MergeSortNonR(int* a, int n);

int* sortArray(int* nums, int numsSize, int* returnSize){
    InsertSort(nums, numsSize);
    *returnSize = numsSize;
    return nums;
}